回答参考：“DFS 的核心不是递归语法，而是后进先出的待办集合。我会先定义访问标记时机，再说明当前路径与已完成节点各代表什么。”

function dfs(graph, start) {
  if (start == null) return []
  const stack = [start]
  const visited = new Set([start])
  const order = []

  while (stack.length) {
    const node = stack.pop()
    order.push(node)
    const neighbors = graph.get(node) ?? []
    for (let i = neighbors.length - 1; i >= 0; i -= 1) {
      const next = neighbors[i]
      if (!visited.has(next)) {
        visited.add(next)
        stack.push(next)
      }
    }
  }
  return order
}

那么如何使用编码来实现深度优先搜索呢？我们继续讨论迷宫问题，这里我给大家一个抽象过后的简单迷宫结构：

图中蓝色的是入口，灰色的是岔路口，黑色的是死胡同，绿色的是出口。

基于眼前的这个迷宫结构，我们来一步一步模拟一下深度优先搜索的具体过程：

• 从 A 出发，沿着唯一的一条道路往下走，遇到了第1个岔路口B。眼前有三个选择：C、D、E。这里我按照从上到下的顺序来走（你也可以按照其它顺序），先走C。
• 发现 C是死胡同，后退到最近的岔路口 B，尝试往D方向走。
• 发现D 是死胡同，，后退到最近的岔路口 B，尝试往E方向走。
• E 是一个岔路口，眼前有两个选择：F 和 G。按照从上到下的顺序来走，先走F。
• 发现F 是死胡同，后退到最近的岔路口 E，尝试往G方向走。
• G 是一个岔路口，眼前有两个选择：H 和 I。按照从上到下的顺序来走，先走H。
• 发现 H 是死胡同，后退到最近的岔路口 G，尝试往I方向走。
• I 就是出口，成功走出迷宫。

大家观察一下这个过程，会不会觉得这些前进、后退的操作，其实和栈结构的入栈、出栈过程非常相似呢？

现在我们把迷宫中的每一个坐标看做是栈里的一个元素，用栈来模拟这个过程：

• 从 A 出发（A入栈），经过了B（B入栈），接下来面临 C、D、E三条路。这里按照从上到下的顺序来走（你也可以选择其它顺序），先走C（C入栈）。
• 发现 C是死胡同，后退到最近的岔路口 B（C出栈），尝试往D方向走（D入栈）。
• E 是一个岔路口，眼前有两个选择：F 和 G。按照从上到下的顺序来走，先走F（F入栈）。
• 发现F 是死胡同，后退到最近的岔路口 E（F出栈），尝试往G方向走（G入栈）。
• G 是一个岔路口，眼前有两个选择：H 和 I。按照从上到下的顺序来走，先走H（H入栈）。
• 发现 H 是死胡同，后退到最近的岔路口 G（H出栈），尝试往I方向走（I入栈）。
• I 就是出口，成功走出迷宫。

此时栈里面的内容就是A、B、E、G、I，因此 A->B->E->G->I 就是走出迷宫的路径。通过深度优先搜索，我们不仅可以定位到迷宫的出口，还可以记录下相关的路径信息。

现在大家知道了深度优先搜索的过程可以转化为一系列的入栈、出栈操作。那么深度优先搜索在编码上一般会如何实现呢？这里，就需要大家回忆一下第 5 节的内容了——DFS 中，我们往往使用递归来模拟入栈、出栈的逻辑。